#include <stdio.h>
#include <stdlib.h>
#include "list.h" // 请不要删除，否则检查不通过

struct token {
    int opt, x;
};

struct token newToken(int opt, int x) {
    struct token t;
    t.opt = opt; t.x = x;
    return t;
}

bool isDigit(char ch) {
    return ch >= '0' && ch <= '9';
}

struct token readToken(char **str) {
    char *ptr = *str;
    if(*ptr == 0) return newToken(0, 0);
    if(!isDigit(*ptr)) {
        char ch = *ptr; int result;
        if(ch == '+') result = 1;
        if(ch == '-') result = 2;
        if(ch == '*') result = 3;
        if(ch == '/') result = 4;
        if(ch == '%') result = 5;
        while(1) {
            *str = ++ptr;
            if(*ptr != ' ') break;
        }
        return newToken(1, result);
    }
    int res = 0;
    while(isDigit(*ptr)) {
        res = res * 10 + *ptr - '0';
        ++ptr;
    }
    while(1) {
        *str = ++ptr;
        if(*ptr != ' ') break;
    }
    return newToken(2, res);
}

int compute_reverse_polish_notation(char *str){
    Stack s;
    init_stack(&s);
    while(1) {
        struct token t = readToken(&str);
        if(t.opt == 0) break;
        if(t.opt == 2) push(&s, t.x);
        if(t.opt == 1) {
            int a, b;
            pop(&s, &b); pop(&s, &a);
            if(t.x == 1) a += b;
            if(t.x == 2) a -= b;
            if(t.x == 3) a *= b;
            if(t.x == 4) a /= b;
            if(t.x == 5) a %= b;
            push(&s, a);
        }
    }
    int x; pop(&s, &x);
    return x;
}